import java.util.Arrays;

/**
 * 剑指 Offer 03. 数组中重复的数字
 */
class Solution {
    public int findRepeatNumber(int[] nums) {
            Arrays.sort(nums);//先排序
            for (int i = 0;i<nums.length-1;i++){
                if (nums[i] - nums[i+1] == 0){//相邻的两个数 相减为0 则为重复
                    return nums[i];
                }
            }
            return 0;
    }
}

/**
 * 剑指 Offer 04. 二维数组中的查找
 */
class Solution2 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        for (int i = 0;i<matrix.length;i++){
            for (int j = 0;j<matrix[0].length;j++){
                if (matrix[i][j] == target){
                    return true;
                }
            }
        }
        return false;
    }
}

class Solution3 {
    public boolean findNumberIn2DArray(int[][] matrix, int target) {
        if (matrix == null || matrix.length == 0){
            return false;
         }
        int row = matrix.length;
        int col = matrix[0].length;
        int rows = 0;
        int cols = col-1;
        while (rows < row && cols >= 0){
            if (matrix[rows][cols] > target){
                cols--;
            }else if (matrix[rows][cols] < target){
                rows++;
            }else{
                return true;
            }
        }
        return false;
    }
}

/**
 * 剑指 Offer 05. 替换空格
 */
class Solution4 {
    public String replaceSpace(String s) {
        StringBuilder ans = new StringBuilder();
        for(int i = 0;i<s.length();i++){
            char ch = s.charAt(i);
            if (ch == ' '){
                ans.append("%20");
            }else{
                ans.append(ch);

            }

        }
        return ans.toString();
    }
}

/**
 * 剑指 Offer 10- I. 斐波那契数列
 */
class Solution5 {
    public int fib(int n) {
        if (n == 1 || n == 2 ){
            return 1;
        }
        if (n == 0){
            return 0;
        }
        int a = 1;
        int b = 1;
        int c = a+b;
        while (n >3){
            a = b;
            b = c;
            c = (a+b)%1000000007;
            n--;
        }
        return c;
    }
}


    /**
     *     剑指 Offer 10- II. 青蛙跳台阶问题
     *     根据斐波那契数列演变
      */
class Solution6 {
    public int numWays(int n) {
        if (n == 0 || n == 1 ){
            return 1;
        }
        int a = 1;
        int b = 1;
        int c = a+b;
        while (n >=3){
            a = b;
            b = c;
            c = (a+b)%1000000007;
            n--;
        }
        return c;
    }
}

/**
 * 剑指 Offer 14- I. 剪绳子
 */
class Solution7 {
    public int cuttingRope(int n) {
/**
 绳子段切分的越多，乘积越大，且3做因数比2更优。

 不断剪去 长度3 并用sum累乘

 把绳子切为多个长度为 3 的片段，则留下的最后一段绳子的长度可能为 0,1,2 三种情况。
 */
        if (n == 1 || n == 2){
            return 1;
        }
        if (n == 3){
            return 2;
        }
        int sum = 1;
        while (n>4){
            sum *=3;
            n -= 3;
        }
        return sum*n;
    }
}